/** typescript实现队列 */

// TypeScript 没有内置的队列类，可以把Array类作为队列来使用
const queue: number[] = [];
queue.push(1);
queue.push(2);
queue.push(3);

/**访问队首元素 */
const peek = queue[0];

/**出队 */
const dequeue = queue.shift();//先进先出

/**判断队列是否为空 */
const isEmpty = queue.length === 0;
/**获取队列的长度 */
const size = queue.length;

// -----------------这些年都在忙什么-----------------
/**基于链表实现队列 */
import { ListNode } from "./链表";
class LinkedListQueue {
  private front: ListNode | null; //头节点
  private rear: ListNode | null; //尾节点
  private queSize: number = 0; //队列长度

  constructor() {
    this.front = null;
    this.rear = null;
  }
  /**获取队列长度 */
  get size(): number { //Getter 方法通常用于访问对象的私有属性，以确保对象的封装性和数据的安全性
    return this.queSize;
  }
  /**判断队列是否为空 */
  isEmpty(): boolean {
    // return this.size === 0; //或者
    return this.queSize === 0;
  }
  /**入队 */
  enqueue(value: number): void {
    const node = new ListNode(value);
    //队列为空，则将头尾节点都指向新节点
    if (!this.front) {
      this.front = node;
      this.rear = node;
    }
    //队列不为空，则将新节点插入到队尾，并更新rear节点
    else {
      this.rear!.next = node;
      this.rear = node;
    }
    this.queSize++;
  }
  /**出队 */
  dequeue(): number | null {
    if (!this.front) {
      throw new Error("Queue is empty");
    }
    const value = this._front;
    this.front = this.front.next;
    this.queSize--;
    return value;
  }
  /**获取队首元素 */
  get _front(): number {
    if (this.queSize === 0) {
      throw new Error("Queue is empty");
    }
    return this.front!.val;
  }

  /**转换数组输出 */
  toArray(): number[] {
    const arr = new Array<number>(this.size); //创建一个长度为队列长度的数组
    let current = this.front;
    while (current) {
      arr.push(current.val);
      current = current.next;
    }
    return arr;
  }
}
// -----------------基于数组实现队列-----------------
/**基于数组实现队列 */
class ArrayQueue {
  private nums: number[];  //使用数组来存储队列元素
  private head: number; //队首指针（首个索引点）
  private queueSize: number = 0; //队列长度

  constructor(capacity: number) {
    this.nums = new Array(capacity);//初始化队列容量
    this.head = 0;
    // this.head + this.queueSize = rear
  }
  /**获取队列容量 */
  get capacity(): number {
    return this.nums.length;
  }
  /**获取队列长度 */
  get size(): number {
    return this.queueSize;
  }
  /**判断队列是否为空 */
  isEmpty(): boolean {
    return this.queueSize === 0;
  }
  /**入队 */
  enqueue(value: number): void {
    if (this.size === this.capacity) {
      throw new Error("Queue is full");
    }
    const rear = (this.head + this.queueSize) % this.capacity; //计算队尾索引
    this.nums[rear] = value;
    this.queueSize++;
  }
  /**出队 */
  dequeue(): number | null {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    const value = this.nums[this.head];
    this.head = (this.head + 1) % this.capacity; //更新队首索引
    this.queueSize--;
    return value;
  }
  /**获取队首元素 */
  get front(): number {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.nums[this.head];
  }
  /**转换数组输出 */
  toArray(): number[] {
    const arr = new Array<number>(this.size);
    for (let i = 0,j = this.head; i < this.size; i++) {
      arr[i] = this.nums[j % this.capacity];
    }
    return arr;
  }
}